// This is unpublished source code. Michah Lerner 2006

package trieMatch.keywordMatcher;

import java.util.List;

/**
 * Implementation of the <strong>TOP</strong> matching criterion ("best"). A stable merge order ensures the top result
 * is <b>consistent</b>, although the top element may not b e optimal when scoring is not distributive as well as
 * commutative.<br>
 * <br>
 * 
 * The stable merge order {@link trieMatch.keywordMatcher.SortedMatchTOP.findMaxMatch} overrides the default "small into
 * large" merge order {@link trieMatch.keywordMatcher.TrieMatcher.findMaxMatch}.
 * 
 * @author Michah.Lerner
 * 
 */

public class SortedtrieMatchTOP extends TrieMatcher {

	public SortedtrieMatchTOP() { // Allocates a sequencer (thread safety)
		super();
	}

	public SortedtrieMatchTOP(final Tiers tiers) { // Allocates a sequencer (thread safety)
		super(tiers);
	}

	public SortedtrieMatchTOP(final Tiers tiers, final Sequencer sequencer) { // Accepts a sequencer
		super(tiers, sequencer);
	}

	// The "top" result depends on merge order, hence consistency needs a stable merge.
	@Override
	List<KMDefinition> findMaxMatch(final Tiers current, final int pos) {
		if (pos >= lookingFor.size()) { return current.instances != null
				? validForMatchtype(current.instances)
				: emptyMatchable; }
		final Tiers nTier = current.successors.get(lookingFor.get(pos).getValue());
		if (nTier != null) {
			final List<KMDefinition> v1 = findMoreMaxMatch(nTier, pos);
			final List<KMDefinition> v2 = findMaxMatch(current, pos + 1);
			if (v1.size() == 0) { return v2; }
			if (v2.size() == 0) { return v1; }
			v1.addAll(v2);
			return v1;
		}
		return findMaxMatch(current, pos + 1);
	}

	@Override
	public List<KMDefinition> findMatch(final String s) {
		lookingFor = sq.arrange(s);
		final List<KMDefinition> res = findMaxMatch(tierHead, 0);
		return (res.size() > 0)
				? res.subList(0, 1)
				: res;
	}
}
